package com.lfg.leetcode.leetcode200;


import java.util.ArrayList;
import java.util.List;

public class No295MedianFinder {

    public static void main(String[] args) {

        int[] array = new int[]{40, 12, 16, 14, 35, 19, 34, 35, 28, 35, 26, 6, 8, 2, 14, 25, 25, 4, 33, 18, 10, 14, 27, 3, 35, 13, 24, 27, 14, 5, 0, 38, 19, 25, 11, 14, 31, 30, 11, 31, 0};
        MedianFinder obj = new MedianFinder();
        for (int i = 0; i < array.length; i++) {
            System.out.println(i + " = " + obj.findMedian());
            int num = array[i];
            obj.addNum(num);
        }

        System.out.println(obj.findMedian());

    }
}

class MedianFinder {

    List<Integer> left = null;
    List<Integer> right = null;

    public MedianFinder() {
        left = new ArrayList<>(100);
        right = new ArrayList<>(100);
    }

    public void addNum(int num) {
        int leftSize = left.size();
        int rightSize = right.size();

        Integer leftVal = null;
        Integer rightVal = null;
        if (leftSize > 0) {
            leftVal = left.get(0);
        }
        if (rightSize > 0) {
            rightVal = right.get(0);
        }

        if ((leftVal == null || num >= leftVal) && (rightVal == null || num <= rightVal)) {
            if (leftSize <= rightSize) {
                left.add(num);
                moveUp(left, 1, left.size(), left.size() / 2 - 1);
            } else {
                right.add(num);
                moveUp(right, 2, right.size(), right.size() / 2 - 1);
                adjust(right, 2);
            }
        } else if (leftVal != null && num < leftVal) {
            if (leftSize > rightSize) {
                left.set(0, num);
                right.add(leftVal);
                moveUp(right, 2, right.size(), right.size() / 2 - 1);
                adjust(left, 1);
            } else {
                left.add(num);
                moveUp(left, 1, left.size(), left.size() / 2 - 1);
            }
        } else {
            if (leftSize >= rightSize) {
                right.add(num);
                moveUp(right, 2, right.size(), right.size() / 2 - 1);
            } else {
                right.set(0, num);
                left.add(rightVal);
                adjust(right, 2);
                moveUp(left, 1, left.size(), left.size() / 2 - 1);
            }
        }
    }

    public double findMedian() {
        if (left.size() != 0 && left.size() == right.size()) {
            return (left.get(0) + right.get(0)) / 2.0;
        } else if (left.size() > right.size()) {
            return left.get(0);
        } else if (left.size() < right.size()) {
            return right.get(0);
        }
        return 0.0;
    }

    public void adjust(List<Integer> list, int operType) {
        int size = list.size();
        for (int i = size / 2 - 1; i >= 0; i--) {
            moveUp(list, operType, size, i);
        }
    }

    private void moveUp(List<Integer> list, int operType, int length, int size) {
        while (size >= 0) {
            int index = 2 * size + 1;
            int right = 2 * size + 2;

            Integer parent = list.get(size);
            if (operType == 2) {
                if (right < length && list.get(right) < list.get(index)) {
                    index = right;
                }
                if (parent > list.get(index)) {
                    list.set(size, list.get(index));
                    list.set(index, parent);
                }
            } else {
                if (right < length && list.get(right) > list.get(index)) {
                    index = right;
                }
                if (parent < list.get(index)) {
                    list.set(size, list.get(index));
                    list.set(index, parent);
                }
            }
            if (size == 0) {
                break;
            }
            size = (size - 1) / 2;
        }
    }

}

